/**
 * hash函数分类
 * 加法Hash
 * 位运算Hash
 * 乘法Hash
 * 除法Hash
 * 查表Hash
 * 混合Has
 */


/**
 * 解决hash冲突的方法
 * 开放定址法: 当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2
 * 拉链法: 这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，
 * 因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
 * 建立公共溢出区: 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
 */


/**
 * 有效的字母异位数
 */

//sort fun
const isAnagram = (str1, str2) => {
  if (str1 === str2) return true
  return str1.split('').sort().join('') === str2.split('').sort().join('')
}

// Map fun
const isAnagramMap = (str1, str2) => {
  if (str1 === str2) return true
  const newmap = new Map()
  str1.split('').forEach((item) => {
    const curValue = newmap.get(item)
    if (curValue === undefined) {
      newmap.set(item, 1)
    } else {
      newmap.set(item, curValue + 1)
    }
  })
  str2.splite('').forEach((item) => {
    if (newmap.has(item)) {
      newmap.set(item, newmap.get(item) - 1)
    } else {
      return false
    }
  })
  return [...newmap.values()].every((item) => item === 0)
}

//hash fun
const isAnagramHash = (str1, str2) => {
  if (str1 === str2) return true
  if (str1.length != str2.length) return false
  let obj = {}
  for (let i = 0; i < str1.length - 1; i++) {
    if (!obj[str1[i]]) {
      obj[str1[i]] = 0
    }
    obj[str1[i]] += 1
    if (!obj[str2[i]]) {
      obj[str2[i]] = 0
    }
    obj[str2[i]] -= 1
    for (let i in obj) {
      if (obj[i] != 0) {
        return false
      }
    }
    return true
  }
}

/**
 * 两数之和
 */
const twoSum = (nums, target) => {
  if (nums.length < 2) return false
  const hash = {}
  for (let i = 0; i < nums.length - 1; i++) {
    if (hash[target - nums[i]] !== undefined) {
      return [i, hash[target - nums[i]]]
    } else {
      hash[nums[i]] = i
    }
  }
  return false
}

/**
 * 三数之和
 * hash表
 */

const threeSum = (nums) => {
  if (nums.length < 3) return null
  let arr = []
  for (let i = 0; i < nums.length - 2; i++) {
    const hash = new Map()
    if (nums[i] > 0) break
    if (nums[i] == nums[i - 1]) continue
    for (let j = i + 1; j < nums.length; j++) {
      const dif = -(nums[i] + nums[j])
      // 去重处理
      // 因为hashMap是首次记录第二次才会push到数组，所以需要判断只有三次重复才能continue
      if (j > i + 2 && nums[j] == nums[j - 1] && nums[j] == nums[j - 2])
        continue
      if (hash.has(dif)) {
        arr.push([nums[i], nums[hash.get(dif)], nums[j]])
        hash.delete(dif)
      }
      hash.set(nums[j], j)
    }
  }
  return arr
}

const threeSumPointer = (nums) => {
  let result = []
  nums = nums.sort()
  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) return result
    if ((nums[i] = nums[i + 1])) continue
    let left = i + 1
    let right = nums.length - 1
    while (left < right) {
      let n1 = nums[i]
      let n2 = nums[left]
      let n3 = nums[right]
      if (n1 + n2 + n3 === 0) {
        result.push([n1, n2, n3])
        while (left < right && nums[left] === n2) left++ //直到指向不一样的数
        while (left < right && nums[right] === n3) right--
      } else if (n1 + n2 + n3 < 0) {
        left++
      } else {
        right--
      }
    }
  }
  return result
}